\defmodule {BinaryTree}

An implementation of \class{EventList} using a binary search tree.
Every event is stored into a tree node which has left and right children.
Using the event time as a comparator %(and also the priority),
the left child is always smaller
than its parent whereas the right is greater or equal.  This allows
an average $O(\log (n))$ time for adding an event
and searching the first event,
where $n$ is the number of events in the structure.
There is less overhead for adding and removing events than splay tree
or red black tree.
However, in the worst case, adding or removing could
be done in time proportional to $n$ because the binary search tree can be turned
into a linked list.

\bigskip\hrule

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{code}
\begin{hide}
/*
 * Class:        BinaryTree
 * Description:  implementation of class EventList using a binary search tree
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author       
 * @since

 * SSJ is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation, either version 3 of the License, or
 * any later version.

 * SSJ is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * A copy of the GNU General Public License is available at
   <a href="http://www.gnu.org/licenses">GPL licence site</a>.
 */
\end{hide}
package umontreal.iro.lecuyer.simevents.eventlist;\begin{hide}

import java.util.Iterator;
import java.util.ListIterator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
import umontreal.iro.lecuyer.util.PrintfFormat;
import umontreal.iro.lecuyer.simevents.Event;
import umontreal.iro.lecuyer.util.PrintfFormat;

/**
 *  Implantation de l'interface EventList ayant comme structure de
 *  donnees un arbre binaire.
 */
\end{hide}

public class BinaryTree implements EventList\begin{hide} {
   // racine de l'arbre
   private Entry root = null;

   // liste d'objets qui peuvent etre reutilises
   private Entry freeEntries = null;

   // compteur de modifications sur l'iterateur.
   private int modCount = 0;\end{hide}
\end{code}\begin{hide}\begin{code}

   public boolean isEmpty()\begin{hide} {
      return root == null;
   }\end{hide}

   public void clear()\begin{hide} {
      while (root != null)
         remove (root);
   }\end{hide}

   public void add (Event ev)\begin{hide} {
      // fonction qui ajoute un evenement dans l'arbre
      // note : si deux evenements ont le meme temps, alors il faut
      //        toujours faire en sorte que ces evenements se retrouvement
      //        comme les fils droits les uns des autres

      Entry cursor = root;
      boolean found = false;

      if (cursor == null)
         root = add (ev, null);
      else {
         while (!found) {
            if (ev.compareTo(cursor.event) < 0) {
               if (cursor.left == null) {
                  cursor.left = add (ev, cursor);
                  found = true;
               }
               cursor = cursor.left;

            } else {
               if (cursor.right == null) {
                  cursor.right = add (ev, cursor);
                  found = true;
               }
               cursor = cursor.right;
            }
         }
      }
      ++modCount;
   }\end{hide}

   public void addFirst (Event ev)\begin{hide} {
   /**
    * Ajoute "ev" comme premier evenement dans l'arbre.
    * Donc completement a gauche
    * On met l'ancien premier evenement a droite de ev.
    * (Necessaire quand on a des evenements simultanes)
    */
      Entry cursor = root;

      if (cursor != null) {
         while (cursor.left != null)
            cursor = cursor.left;

         Entry e = add (ev, cursor.father);
         e.right = cursor;
         if (cursor == root)
            root = e;
         else
            cursor.father.left = e;
         cursor.father = e;
      }
      else
         root = add (ev, null);

      ++modCount;
   }\end{hide}

   public void addBefore (Event ev, Event other)\begin{hide} {
      Entry otherEntry = findEntry (other);
      Entry evEntry    = add (ev , null);

      if (otherEntry == null)
         throw new IllegalArgumentException("other not in the tree");

      // insere evEntry a la place de otherEntry et otherEntry
      // devient le fils droit de evEntry
      if (otherEntry != root) {
         if (otherEntry == otherEntry.father.right)
            otherEntry.father.right = evEntry;
         else
            otherEntry.father.left = evEntry;
      }
      else
         root = evEntry;

      evEntry.father = otherEntry.father;
      otherEntry.father   = evEntry;
      evEntry.right   = otherEntry;

      // le ss-arbre de droite de otherEntry devient le
      // ss-arbre de droite de evEntry
      // permet que evEntry soit exactement apres
      // otherEntry qu'importe les operations effectuees
      evEntry.left  = otherEntry.left;

      if (evEntry.left != null)
         evEntry.left.father  = evEntry;

      otherEntry.left = null;

      ++modCount;
   }\end{hide}

   public void addAfter (Event ev, Event other)\begin{hide} {
      // on va chercher le "Entry" de other
      Entry otherEntry = findEntry (other);

      if (otherEntry == null)
         throw new IllegalArgumentException("other not in the tree");

      // otherEntry est le parent de evEntry
      Entry evEntry = add (ev, otherEntry);

      evEntry.right = otherEntry.right;
      otherEntry.right = evEntry;

      if (evEntry.right != null)
         evEntry.right.father = evEntry;

      ++modCount;
   }\end{hide}

   public Event getFirst()\begin{hide} {
      if (root==null)
         return null;
      Entry cursor = root;
      while (cursor.left != null)
         cursor = cursor.left;
      return cursor.event;
   }\end{hide}

   public Event getFirstOfClass (String cl)\begin{hide} {
      Entry cursor = root;
      if (root != null)
         while (cursor.left != null)
            cursor = cursor.left;

      while (cursor != null) {
         if (cursor.event.getClass().getName().equals (cl))
            return cursor.event;
         cursor = successor (cursor);
      }
      return null;
   }

   @SuppressWarnings("unchecked")
   public <E extends Event> E getFirstOfClass (Class<E> cl) {
      Entry cursor = root;
      if (root != null)
         while (cursor.left != null)
            cursor = cursor.left;

      while (cursor != null) {
         if (cursor.event.getClass() == cl)
            return (E)cursor.event;
         cursor = successor (cursor);
      }
      return null;
   }

   public Iterator<Event> iterator() {
      return listIterator();
   }

   public ListIterator<Event> listIterator() {
      return new BTItr();
   }\end{hide}

   public boolean remove (Event ev)\begin{hide} {
      Entry evEntry = findEntry(ev);
      if (evEntry == null)
         return false;
      else
         return remove(evEntry);
   }\end{hide}

   public Event removeFirst()\begin{hide} {
      if (root == null)
         return null;

      Entry cursor = root;
      while (cursor.left != null)
         cursor = cursor.left;

      Event first = cursor.event;
      remove(cursor);

      return first;
   }\end{hide}

   public String toString()\begin{hide} {
      StringBuffer sb = new StringBuffer ("Contents of the event list BinaryTree:");
      Entry cursor = root;

      if (root != null)
         while (cursor.left != null)
            cursor = cursor.left;

      while (cursor != null) {
         sb.append (PrintfFormat.NEWLINE +
                    PrintfFormat.g (12, 7, cursor.event.time()) + ", " +
                    PrintfFormat.g (8, 4, cursor.event.priority()) +
                    " : " + cursor.event.toString());
         cursor = successor (cursor);
      }

      return sb.toString();
   }

   private Entry add (Event ev, Entry father) {
      // On regarde la liste freeEntries
      if (freeEntries != null) {
         Entry tempo = freeEntries;
         freeEntries = freeEntries.right;
         tempo.event = ev;
         tempo.left  = null;
         tempo.right = null;
         tempo.father = father;
         return tempo;
      }
      // on cree un nouvel objet
      else
         return new Entry(ev, null, null, father);
   }

   private boolean remove (Entry e) {
      boolean filsGauche = false;
      boolean isRoot = false;
      Entry cursor;

      if (e == root)
         isRoot = true;
      else {
         if (e == e.father.left)
            filsGauche = true;
         else
            filsGauche = false;
      }

      // Si condition vrai, a un fils droit ou rien
      if (e.left == null) {
         if (isRoot)
            root = e.right;
         else if (filsGauche)
            e.father.left = e.right;
         else
            e.father.right = e.right;

         if (e.right != null)
            e.right.father = e.father;
      }
      else if (e.right == null) {
         // Si condition vrai,  a uniquement un fils gauche
         if (isRoot)
            root = e.left;
         else if (filsGauche)
            e.father.left = e.left;
         else
            e.father.right = e.left;
         e.left.father = e.father;
      }
      else {
         // a 2 fils
         // recherche son descendant le plus petit dans le ss-arbre de droite
         // et remplace "e" par ce descendant

         cursor = e.right;
         if (cursor.left == null) {
            // c'est son fils de droite
            if (isRoot)
               root = cursor;
            else {
               if (filsGauche)
                  e.father.left = cursor;
               else
                  e.father.right = cursor;
            }
            cursor.left = e.left;
         }
         else {
            // recherche de la plus petite valeur dans le ss-arbre droit
            while (cursor.left != null)
               cursor = cursor.left;

            // echange entre e et cursor et elimination de e
            cursor.father.left = cursor.right;

            if (isRoot)
               root = cursor;
            else if (filsGauche)
               e.father.left = cursor;
            else
               e.father.right = cursor;

            cursor.father.left = cursor.right;
            if (cursor.right != null)
               cursor.right.father = cursor.father;

            cursor.right = e.right;
            cursor.left  = e.left;
            e.right.father = cursor;
         }

         cursor.father = e.father;
         e.left.father = cursor;
      }

      // recupere l'espace du noeud
      e.right = freeEntries;
      e.left =  null;
      e.event = null;
      freeEntries = e;
      e = null;
      ++modCount;
      return true;
   }

   private Entry successor (Entry cursor) {
      if (cursor == null)
         return null;

      if (cursor.right != null) {
         cursor = cursor.right;
         while (cursor.left != null)
            cursor = cursor.left;
      }
      else {
         while (cursor.father != null && cursor.father.right == cursor)
            cursor = cursor.father;
         cursor = cursor.father;
      }
      return cursor;
   }

   /**
    * fonction qui trouve le noeud (Entry) d'un evenement
    * dans l'arbre
    */
   private Entry findEntry (Event ev) {
      Entry cursor = root;
      while (cursor != null) {
         if (cursor.event == ev)
            return cursor;
         else if (ev.compareTo(cursor.event) < 0)
            cursor = cursor.left;
         else
            cursor = cursor.right;
      }
      return null;
   }

   private Entry predecessor (Entry cursor) {
      if (cursor == null)
         return null;

      if (cursor.left != null) {
         cursor = cursor.left;
         while (cursor.right != null)
            cursor = cursor.right;
      }
      else {
         while (cursor.father != null && cursor.father.left == cursor)
            cursor = cursor.father;
         cursor = cursor.father;
      }
      return cursor;
   }

   /**
    * Classe interne representant les noeuds de l'arbre
    */
   private static class Entry  {
      Event event;
      Entry right;
      Entry left;
      Entry father;

      Entry (Event event, Entry left, Entry right, Entry father) {
         this.event = event;
         this.left = left;
         this.right = right;
         this.father = father;
      }
   }

   private class BTItr implements ListIterator<Event> {
      private Entry prev;
      private Entry next;
      private Entry lastRet;
      private int expectedModCount;
      private int nextIndex;

      BTItr() {
         prev = null;
         next = root;
         if (next != null) {
            while (next.left != null)
               next = next.left;
         }
         expectedModCount = modCount;
         lastRet = null;
         nextIndex = 0;
      }

      public void add(Event ev) {
         if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

         // Check the event time and priority
         if (next != null && ev.compareTo(next.event) > 0) {
            ev.setTime (next.event.time());
            ev.setPriority (next.event.priority());
         }
         if (prev != null && ev.compareTo(prev.event) < 0) {
            ev.setTime (prev.event.time());
            ev.setPriority (prev.event.priority());
         }

         Entry e = BinaryTree.this.add (ev, next);
         if (prev != null) {
            // Ajouter ev apr`es prev.
            // insere e comme fils droit de prev
            e.father = prev;
            e.right = prev.right;
            prev.right = e;
            if (e.right != null)
               e.right.father = e;
         }
         else {
            // ajoute ev avant next.
            // insere e a la place de eo et eo devient le fils droit de e
            if (next != root) {
               if (next == next.father.left)
                  next.father.left = e;
               else
                  next.father.right = e;
            }
            else
               root = e;
            e.father = prev.father;
            prev.father = e;
            e.left = prev;
            // le ss-arbre de droite de eo devient le ss-arbre de droite de e
            // permet que e soit exactement apres eo qu'importe les
            // operations effectuees
            e.right = prev.right;
            if (e.right != null)
               e.right.father = e;
            prev.right = null;
         }

         prev = e;
         ++nextIndex;
         lastRet = null;
         ++modCount;
         ++expectedModCount;
      }

      public boolean hasNext() {
         if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
         return next != null;
      }

      public boolean hasPrevious() {
         if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
         return prev != null;
      }

      public Event next() {
         if (!hasNext())
            throw new NoSuchElementException();

         ++nextIndex;
         Event ev = next.event;
         lastRet = next;
         prev = next;
         next = successor (next);
         return ev;
      }

      public int nextIndex() {
         if (!hasNext())
            throw new NoSuchElementException();

         return nextIndex;
      }

      public Event previous() {
         if (!hasPrevious())
            throw new NoSuchElementException();

         --nextIndex;
         Event ev = prev.event;
         lastRet = prev;
         next = prev;
         prev = predecessor (prev);
         return ev;
      }

      public int previousIndex() {
         if (!hasPrevious())
            throw new NoSuchElementException();

         return nextIndex - 1;
      }

      public void remove() {
         if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
         if (lastRet == null)
            throw new IllegalStateException();

         if (lastRet == next) // Last call to previous
            next = successor (next);
         else { // Last call to next or no call
            prev = predecessor (prev);
            --nextIndex;
         }
         BinaryTree.this.remove (lastRet);
         lastRet = null;
         ++expectedModCount;
      }

      public void set (Event ev) {
         if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
         if (lastRet == null)
            throw new IllegalStateException();

         Entry pred = predecessor (lastRet);
         Entry succ = successor (lastRet);
         if (pred != null && ev.compareTo(pred.event) < 0) {
            ev.setTime (pred.event.time());
            ev.setPriority (pred.event.priority());
         }
         if (succ != null && ev.compareTo(succ.event) > 0) {
            ev.setTime (succ.event.time());
            ev.setPriority (succ.event.priority());
         }
         lastRet.event = ev;
      }
   }

/*   public static void main (String[] args) {
      BinaryTree sp = new BinaryTree();

      Event1 e1 = new Event1(); e1.setTime(10.0);
      Event1 e2 = new Event1(); e2.setTime(20.0);
      Event1 e3 = new Event1(); e3.setTime(30.0);
      Event1 e4 = new Event1(); e4.setTime(40.0);
      Event1 e5 = new Event1(); e5.setTime(50.0);
      Event1 e6 = new Event1(); e6.setTime(60.0);
      Event1 e7 = new Event1(); e7.setTime(70.0);

      sp.add(e1);
      sp.add(e2);
      sp.print2(sp.root);
      sp.add(e3);
      sp.print2(sp.root);
      sp.add(e4);
      sp.print2(sp.root);
      sp.add(e5);
      sp.print2(sp.root);
      sp.add(e6);
      sp.print2(sp.root);
      sp.add(e7);
      sp.print2(sp.root);
      // sp.add(e5);
      // sp.print2(sp.root);
      sp.add(e7);
      sp.print2(sp.root);
      // sp.add(e5);
      // sp.print2(sp.root);

      sp.getFirst();
      System.out.println(".....after GetFirst" +
                         PrintfFormat.NEWLINE +
                         PrintfFormat.NEWLINE +
                         PrintfFormat.NEWLINE);
      sp.print2(sp.root);
      sp.remove(e3);
      System.out.println("Apres remove" + PrintfFormat.NEWLINE);
      sp.print2(sp.root);
   }

   private void print(Entry t) {
      if (t != null){
         print (t.left);
         System.out.println ("===========> Event time "+t.event.time());
         print (t.right);
      }
   }

   private void print2(Entry t) {
      System.out.println("===============================  "+
                         "print2 : pour ..... "+t.event.time());
      if (t != null) {
         System.out.println ("===========> ev time   "+t.event.time());
         gauche (t.left);
         droite (t.right);
         System.out.println();
      }
      else
         System.out.println ("===========> gauche  null ");
   }

   private void gauche (Entry t) {
      if (t != null) {
         System.out.println ("===========> gauche   "+t.event.time());
         gauche (t.left);
         droite (t.right);
         System.out.println();
      }
      else
         System.out.println ("===========> gauche  null ");
   }

   private void droite (Entry t) {
      if (t != null){
         System.out.println ("===========> droite  "+t.event.time());
         gauche (t.left);
         droite (t.right);
         // System.out.println();
      }
      else
         System.out.println ("===========> droite  null ");
   }

   private static class Event1 extends Event {
      public void actions() {}

      public String toString() {
         return "Event(" + eventTime + ")";
      }
   };





*/
   /*
        public  BinaryTree() {

      Event1 e1 = new Event1(); e1.setTime(7.0);
      Event1 e2 = new Event1(); e2.setTime(5.0);
      Event1 e3 = new Event1(); e3.setPriority(2); e3.setTime(5.0);
      Event1 e4 = new Event1(); e4.setTime(6.0);
      Event1 e5 = new Event1(); e5.setPriority(2); e5.setTime(10.0);
      Event1 e6 = new Event1(); e6.setTime(9.0);
      Event1 e7 = new Event1(); e7.setTime(11.0);

        add(e1);
        add(e2);
        add(e3);
        add(e4);
        add(e5);
        add(e6);
        add(e7);
        print22(root);
        remove (e5);
        print22(root);

        }



        public void print22(Entry t) {
        System.out.println("racine............ ..... "+t.event.time());
        gauche2(t.left);
        droite2(t.right);
        System.out.println();

        }



        public void gauche2 (Entry t) {
        if (t!=null){
        System.out.println ("===========> gauche   "+t.event.time());
        gauche2(t.left);
        droite2(t.right);
        System.out.println();

        }
        else System.out.println ("===========> gauche  null ");
        }

        public void droite2 (Entry t) {
        if (t!=null){
        System.out.println ("===========> droite  "+t.event.time());
        gauche2(t.left);
        droite2(t.right);
        // System.out.println();

        }
        else System.out.println ("===========> droite  null ");
        }
   */
}\end{hide}
\end{code}
\end{hide}
